package targetToOffer.sixthDay;

/**
 * @author Godc
 * @description
 */
public class MaxSubArray {
    public static void main(String[] args) {
        MaxSubArraySolution s = new MaxSubArraySolution();
        int[] ints = {1,2};
        int i = s.maxSubArray1(ints);
        System.out.println(i);
    }
}
class MaxSubArraySolution {
    public int maxSubArray(int[] nums) {
        //dp[i]表示包含i截尾的数组的最大和
        //递推公式：dp[i] = dp[i-1]+nums[i]（dp[i-1]>0）,dp[i] = nums[i]（dp[i-1]<=0）
        //初始化：dp[0]=nums[0]
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if(dp[i-1]>0) dp[i] = dp[i-1]+nums[i];
            else dp[i] = nums[i];
            if(dp[i]>max) max = dp[i];
        }
        return max;
    }

    /**
     * 状态压缩
     * @param nums
     * @return
     */
    public int maxSubArray1(int[] nums){
        int prev = 0,cur = nums[0],max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            if(prev>0) cur+=nums[i];
            else cur = nums[i];
            prev = cur;
            if(cur>max) max = cur;
        }
        return max;
    }
}
